<!DOCTYPE html>
<html lang=zh>
<head>
  <meta charset="utf-8">
  
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, minimum-scale=1, user-scalable=no, minimal-ui">
  <meta name="renderer" content="webkit">
  <meta http-equiv="Cache-Control" content="no-transform" />
  <meta http-equiv="Cache-Control" content="no-siteapp" />
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="apple-mobile-web-app-status-bar-style" content="black">
  <meta name="format-detection" content="telephone=no,email=no,adress=no">
  <!-- Color theme for statusbar -->
  <meta name="theme-color" content="#000000" />
  <!-- 强制页面在当前窗口以独立页面显示,防止别人在框架里调用页面 -->
  <meta http-equiv="window-target" content="_top" />
  
  
  <title>Javascript实现寻找哈密尔顿回路 | DiDi</title>
  <meta name="description" content="哈密尔顿回路首先我们了解下什么是哈密尔顿回路，简单解释就是，有一个无向连通图 G（具有顶点和边的图），他有 N 个顶点，从任意一个顶点出发，所有的顶点有且只经过一次，如果最后可以回到起点则我们称这个连通图 G 拥有哈密尔顿回路。网上大多都能搜索到通过 Java，.Net 语言实现的查找哈密尔顿回路的代码，今天我将带大家一起通过 javascript 实现查找哈密尔顿的方法。 无向连通图 如上图所示">
<meta property="og:type" content="article">
<meta property="og:title" content="Javascript实现寻找哈密尔顿回路">
<meta property="og:url" content="https://guoyayunhappy.gitee.io/didiblog/2024/03/03/find-hamilton-path/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="哈密尔顿回路首先我们了解下什么是哈密尔顿回路，简单解释就是，有一个无向连通图 G（具有顶点和边的图），他有 N 个顶点，从任意一个顶点出发，所有的顶点有且只经过一次，如果最后可以回到起点则我们称这个连通图 G 拥有哈密尔顿回路。网上大多都能搜索到通过 Java，.Net 语言实现的查找哈密尔顿回路的代码，今天我将带大家一起通过 javascript 实现查找哈密尔顿的方法。 无向连通图 如上图所示">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://guoyayunhappy.gitee.io/didiblog/images/hamiltonPath.png">
<meta property="article:published_time" content="2024-03-03T00:18:45.000Z">
<meta property="article:modified_time" content="2025-07-18T23:32:10.759Z">
<meta property="article:author" content="John Doe">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://guoyayunhappy.gitee.io/didiblog/images/hamiltonPath.png">
  <!-- Canonical links -->
  <link rel="canonical" href="https://guoyayunhappy.gitee.io/didiblog/2024/03/03/find-hamilton-path/index.html">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="icon" href="images/favatar/idesign-logo.png" type="image/x-icon">
  
  
<link rel="stylesheet" href="/didiblog/css/style.css">

  
  
  
  
<meta name="generator" content="Hexo 7.3.0"></head>


<body class="main-center theme-black" itemscope itemtype="http://schema.org/WebPage">
  <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  <div class="slimContent">
    <div class="navbar-header">
      
      
      <div class="profile-block text-center">
        <a id="avatar" href="https://gitee.com/GuoyayunHappy" target="_blank">
          <img class="img-circle img-rotate" src="/didiblog/images/avatar.jpg" width="200" height="200">
        </a>
        <h2 id="name" class="hidden-xs hidden-sm">一枚@大帅锅</h2>
        <h3 id="title" class="hidden-xs hidden-sm hidden-md">CV工程师</h3>
        <small id="location" class="text-muted hidden-xs hidden-sm"><i class="icon icon-map-marker"></i> Shanghai, China</small>
      </div>
      
      <div class="search" id="search-form-wrap">

    <form class="search-form sidebar-form">
        <div class="input-group">
            <input type="text" class="search-form-input form-control" placeholder="搜索" />
            <span class="input-group-btn">
                <button type="submit" class="search-form-submit btn btn-flat" onclick="return false;"><i class="icon icon-search"></i></button>
            </span>
        </div>
    </form>
    <div class="ins-search">
  <div class="ins-search-mask"></div>
  <div class="ins-search-container">
    <div class="ins-input-wrapper">
      <input type="text" class="ins-search-input" placeholder="想要查找什么..." x-webkit-speech />
      <button type="button" class="close ins-close ins-selectable" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">×</span></button>
    </div>
    <div class="ins-section-wrapper">
      <div class="ins-section-container"></div>
    </div>
  </div>
</div>


</div>
      <button class="navbar-toggle collapsed" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false">
        <span class="sr-only">Toggle navigation</span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
        <span class="icon-bar"></span>
      </button>
    </div>
    <nav id="main-navbar" class="collapse navbar-collapse" itemscope itemtype="http://schema.org/SiteNavigationElement" role="navigation">
      <ul class="nav navbar-nav main-nav menu-highlight">
        
        
        <li class="menu-item menu-item-home">
          <a href="/didiblog/.">
            
            <i class="icon icon-home-fill"></i>
            
            <span class="menu-title">首页</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-archives">
          <a href="/didiblog/archives">
            
            <i class="icon icon-archives-fill"></i>
            
            <span class="menu-title">归档</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-categories">
          <a href="/didiblog/categories">
            
            <i class="icon icon-folder"></i>
            
            <span class="menu-title">分类</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-tags">
          <a href="/didiblog/tags">
            
            <i class="icon icon-tags"></i>
            
            <span class="menu-title">标签</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-links">
          <a href="/didiblog/links">
            
            <i class="icon icon-friendship"></i>
            
            <span class="menu-title">友链</span>
          </a>
        </li>
        
        
        <li class="menu-item menu-item-about">
          <a href="/didiblog/about">
            
            <i class="icon icon-cup-fill"></i>
            
            <span class="menu-title">关于</span>
          </a>
        </li>
        
      </ul>
      
	
    <ul class="social-links">
    	
        <li><a href="https://gitee.com/GuoyayunHappy" target="_blank" title="Github" data-toggle=tooltip data-placement=top><i class="icon icon-github"></i></a></li>
        
        <li><a href="/didiblog/atom.xml" target="_blank" title="Rss" data-toggle=tooltip data-placement=top><i class="icon icon-rss"></i></a></li>
        
    </ul>

    </nav>
  </div>
</header>

  
    <aside class="sidebar" itemscope itemtype="http://schema.org/WPSideBar">
  <div class="slimContent">
    
      <div class="widget">
    <h3 class="widget-title">公告</h3>
    <div class="widget-body">
        <div id="board">
            <div class="content">
                <p>让coding更有趣!</p>
            </div>
        </div>
    </div>
</div>

    
      
  <div class="widget">
    <h3 class="widget-title">分类</h3>
    <div class="widget-body">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/didiblog/categories/JS/">JS</a><span class="category-list-count">6</span></li><li class="category-list-item"><a class="category-list-link" href="/didiblog/categories/TS/">TS</a><span class="category-list-count">1</span></li><li class="category-list-item"><a class="category-list-link" href="/didiblog/categories/%E7%BD%91%E7%AB%99/">网站</a><span class="category-list-count">1</span><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/didiblog/categories/%E7%BD%91%E7%AB%99/html/">html</a><span class="category-list-count">1</span></li></ul></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签</h3>
    <div class="widget-body">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/HTML/" rel="tag">HTML</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/HTTP/" rel="tag">HTTP</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/HTTPS/" rel="tag">HTTPS</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/JS/" rel="tag">JS</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/Nodejs/" rel="tag">Nodejs</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/Token/" rel="tag">Token</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/cookie/" rel="tag">cookie</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/js/" rel="tag">js</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/typescript/" rel="tag">typescript</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96/" rel="tag">性能优化</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/%E7%BC%93%E5%AD%98/" rel="tag">缓存</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" rel="tag">设计模式</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/didiblog/tags/%E8%B7%A8%E5%9F%9F/" rel="tag">跨域</a><span class="tag-list-count">1</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">标签云</h3>
    <div class="widget-body tagcloud">
      <a href="/didiblog/tags/HTML/" style="font-size: 13px;">HTML</a> <a href="/didiblog/tags/HTTP/" style="font-size: 13px;">HTTP</a> <a href="/didiblog/tags/HTTPS/" style="font-size: 13px;">HTTPS</a> <a href="/didiblog/tags/JS/" style="font-size: 13px;">JS</a> <a href="/didiblog/tags/Nodejs/" style="font-size: 13px;">Nodejs</a> <a href="/didiblog/tags/Token/" style="font-size: 13px;">Token</a> <a href="/didiblog/tags/cookie/" style="font-size: 13px;">cookie</a> <a href="/didiblog/tags/js/" style="font-size: 13px;">js</a> <a href="/didiblog/tags/typescript/" style="font-size: 13px;">typescript</a> <a href="/didiblog/tags/%E6%80%A7%E8%83%BD%E4%BC%98%E5%8C%96/" style="font-size: 13px;">性能优化</a> <a href="/didiblog/tags/%E7%AE%97%E6%B3%95/" style="font-size: 13.5px;">算法</a> <a href="/didiblog/tags/%E7%BC%93%E5%AD%98/" style="font-size: 13px;">缓存</a> <a href="/didiblog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" style="font-size: 14px;">设计模式</a> <a href="/didiblog/tags/%E8%B7%A8%E5%9F%9F/" style="font-size: 13px;">跨域</a>
    </div>
  </div>

    
      
  <div class="widget">
    <h3 class="widget-title">归档</h3>
    <div class="widget-body">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2025/07/">七月 2025</a><span class="archive-list-count">2</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2025/06/">六月 2025</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2024/03/">三月 2024</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2024/02/">二月 2024</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2023/12/">十二月 2023</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2023/10/">十月 2023</a><span class="archive-list-count">1</span></li><li class="archive-list-item"><a class="archive-list-link" href="/didiblog/archives/2023/02/">二月 2023</a><span class="archive-list-count">7</span></li></ul>
    </div>
  </div>


    
      
  <div class="widget">
    <h3 class="widget-title">最新文章</h3>
    <div class="widget-body">
      <ul class="recent-post-list list-unstyled no-thumbnail">
        
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/didiblog/2025/07/28/browser-cache/" class="title">用代码实践浏览器的强缓存和协商缓存</a>
              </p>
              <p class="item-date">
                <time datetime="2025-07-28T06:54:53.000Z" itemprop="datePublished">2025-07-28</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                <a class="category-link" href="/didiblog/categories/JS/">JS</a>
              </p>
              <p class="item-title">
                <a href="/didiblog/2025/07/18/tail-call-optimization/" class="title">尾调用优化</a>
              </p>
              <p class="item-date">
                <time datetime="2025-07-18T11:53:08.000Z" itemprop="datePublished">2025-07-18</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/didiblog/2025/06/17/interview/" class="title">interview</a>
              </p>
              <p class="item-date">
                <time datetime="2025-06-17T03:52:38.000Z" itemprop="datePublished">2025-06-17</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/didiblog/2024/03/03/find-hamilton-path/" class="title">Javascript实现寻找哈密尔顿回路</a>
              </p>
              <p class="item-date">
                <time datetime="2024-03-03T00:18:45.000Z" itemprop="datePublished">2024-03-03</time>
              </p>
            </div>
          </li>
          
          <li>
            
            <div class="item-inner">
              <p class="item-category">
                
              </p>
              <p class="item-title">
                <a href="/didiblog/2024/02/21/better-to-know-signature-and-certificate/" class="title">一文读懂加密，摘要，数字签名和证书</a>
              </p>
              <p class="item-date">
                <time datetime="2024-02-21T03:22:45.000Z" itemprop="datePublished">2024-02-21</time>
              </p>
            </div>
          </li>
          
      </ul>
    </div>
  </div>
  

    
  </div>
</aside>

  
  
<main class="main" role="main">
  <div class="content">
  <article id="post-find-hamilton-path" class="article article-type-post" itemscope itemtype="http://schema.org/BlogPosting">
    
    <div class="article-header">
      
        
  
    <h1 class="article-title" itemprop="name">
      Javascript实现寻找哈密尔顿回路
    </h1>
  

      
      <div class="article-meta">
        <span class="article-date">
    <i class="icon icon-calendar-check"></i>
	<a href="/didiblog/2024/03/03/find-hamilton-path/" class="article-date">
	  <time datetime="2024-03-03T00:18:45.000Z" itemprop="datePublished">2024-03-03</time>
	</a>
</span>
        
        
  <span class="article-tag">
    <i class="icon icon-tags"></i>
	<a class="article-tag-link-link" href="/didiblog/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a>
  </span>


        

        <span class="post-comment"><i class="icon icon-comment"></i> <a href="/didiblog/2024/03/03/find-hamilton-path/#comments" class="article-comment-link">评论</a></span>
        
      </div>
    </div>
    <div class="article-entry marked-body" itemprop="articleBody">
      
        <h1 id="哈密尔顿回路"><a href="#哈密尔顿回路" class="headerlink" title="哈密尔顿回路"></a>哈密尔顿回路</h1><p>首先我们了解下什么是哈密尔顿回路，简单解释就是，有一个无向连通图 G（具有顶点和边的图），他有 N 个顶点，从任意一个顶点出发，所有的顶点有且只经过一次，如果最后可以回到起点则我们称这个连通图 G 拥有哈密尔顿回路。网上大多都能搜索到通过 Java，.Net 语言实现的查找哈密尔顿回路的代码，今天我将带大家一起通过 javascript 实现查找哈密尔顿的方法。</p>
<h2 id="无向连通图"><a href="#无向连通图" class="headerlink" title="无向连通图"></a>无向连通图</h2><p><img src="/didiblog/images/hamiltonPath.png" alt="image.png"></p>
<p>如上图所示，是一个简单的无向（忽略箭头，没找到不带箭头的连接线…）连通图，它拥有 A,B,C,D,E,F 共 6 个顶点，同时顶点之间还有边将两个顶点连接起来。那如何证明这个图拥有哈密尔顿回路并正确的返回这个回路的顶点路径集合呢?</p>
<h2 id="实现寻找哈密尔顿回路"><a href="#实现寻找哈密尔顿回路" class="headerlink" title="实现寻找哈密尔顿回路"></a>实现寻找哈密尔顿回路</h2><h3 id="创建GraphG类"><a href="#创建GraphG类" class="headerlink" title="创建GraphG类"></a>创建<code>GraphG</code>类</h3><p>首先我们创建一个 js 文件，然后在文件内部创建一个类<code>GraphG</code>.我们设想一下，这个类应该有哪些方法？</p>
<ul>
<li>可以添加一个顶点</li>
<li>可以将两个顶点连接起来</li>
<li>可以判断两个顶点之间有没有边（是否关联）</li>
</ul>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">class GraphG &#123;</span><br><span class="line">  constructor() &#123;</span><br><span class="line">    this.vertices = []; //顶点集合</span><br><span class="line">    this.adjList = new Map(); //顶点关联集合</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  //添加一个顶点</span><br><span class="line">  addVertex(v) &#123;</span><br><span class="line">    this.vertices.push(v);</span><br><span class="line">    this.adjList.set(v, []); //初始化关联顶点为空</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  //把两个顶点相关联</span><br><span class="line">  linkVertex(v, w) &#123;</span><br><span class="line">    // 如果两个顶点不存在，则返回</span><br><span class="line">    if (!this.vertices.includes(v) || !this.vertices.includes(w)) &#123;</span><br><span class="line">      return;</span><br><span class="line">    &#125;</span><br><span class="line">    // 把两个顶点分别放到彼此的Map集合里</span><br><span class="line">    this.adjList.get(v).push(w);</span><br><span class="line">    this.adjList.get(w).push(v);</span><br><span class="line">  &#125;</span><br><span class="line"></span><br><span class="line">  //顶点v，w是否关联(是否存在边)</span><br><span class="line">  hasEdge(v, w) &#123;</span><br><span class="line">    return this.adjList.get(v).includes(w);</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="编写实现函数"><a href="#编写实现函数" class="headerlink" title="编写实现函数"></a>编写实现函数</h3><p>接下来我们需要这样一个函数，它接受一个无向连通图，然后经过一系列计算判断这个图是否存在哈密尔顿回路，如果存在则返回这个回路的顶点路径集合，如果不存在则返回空。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line">class Hamilton &#123;</span><br><span class="line">  constructor(graph) &#123;</span><br><span class="line">    this.hamiltonPath = [];</span><br><span class="line">    this.graph = graph;</span><br><span class="line">  &#125;</span><br><span class="line">  findHamiltonPath() &#123;</span><br><span class="line">    const firstVertex = this.graph.vertices[0];</span><br><span class="line">    this.hamiltonPath.push(firstVertex); //把第一个顶点放到回路里</span><br><span class="line">    if (this.getPath(firstVertex, firstVertex)) &#123;</span><br><span class="line">      return this.hamiltonPath;</span><br><span class="line">    &#125;</span><br><span class="line">    return [];</span><br><span class="line">  &#125;</span><br><span class="line">  getPath(vertex, originalVertex) &#123;</span><br><span class="line">      //回路包含所有的路径</span><br><span class="line">    if (this.hamiltonPath.length === this.graph.vertices.length) &#123;</span><br><span class="line">        //并且最后两个顶点之间有边</span><br><span class="line">      if (this.graph.hasEdge(vertex, originalVertex)) &#123;</span><br><span class="line">        this.hamiltonPath.push(originalVertex);</span><br><span class="line">        return true;</span><br><span class="line">      &#125;</span><br><span class="line">      return false;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    for (let i = 0; i &lt; this.graph.adjList.get(vertex).length; i++) &#123;</span><br><span class="line">      const nextVertex = this.graph.adjList.get(vertex)[i]; // 取出一个关联的顶点；</span><br><span class="line">      if (this.hamiltonPath.includes(nextVertex)) &#123;</span><br><span class="line">        continue; //如果这个顶点已经放到回路路径集合里了则直接跳过</span><br><span class="line">      &#125;</span><br><span class="line">      this.hamiltonPath.push(nextVertex); //添加到回路集合里</span><br><span class="line">      if (this.getPath(nextVertex, this.graph.vertices[0])) &#123;</span><br><span class="line">        //查看有没有结束</span><br><span class="line">        return true;</span><br><span class="line">      &#125;</span><br><span class="line">      this.hamiltonPath.pop(); //不符合哈密尔顿回路把最新的一个取出来</span><br><span class="line">    &#125;</span><br><span class="line">    return false;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>通过分析上面代码我们可以看出，首先声明一个哈密尔顿回路的集合数组<code>hamiltonPath</code>,然后取第一个顶点作为起始点，通过方法<code>getPath</code>去比较，首先判断当前哈密尔顿回路是否把所有的顶点都放进来了，如果是则可以最后判断这个传进来的顶点（第一个参数 vertex）跟第一个顶点是否有边，如果有说明此图拥有无向连通图，将路径的数组集合返回即可。如果这个路径集合还没有包含所有顶点则需要继续往下找。思路大致如下：</p>
<ul>
<li>循环当前的顶点，找到所有它关联的顶点</li>
<li>取出一个关联的顶点，查看它是否已经在回路集合里了，如果有就跳过 （见 26~29 行代码）</li>
<li>如果不存在回路集合里，则把它添加到路径集合里 <code>this.hamiltonPath.push(nextVertex);</code></li>
<li>重点来了，这时候再拿这个顶点去跟第一个顶点比较，看是否满足条件（这里会又进入<code>getPath</code>方法内去递推），如果不满足则把这个顶点从回路集合里拿出来（回溯）<code>this.hamiltonPath.pop(); //不符合哈密尔顿回路把最新的一个取出来</code>。如果满足则说明找到哈密尔顿回路。</li>
<li>如果所有循环都走完了也没有发现，就返回 false（第 37 行代码）</li>
</ul>
<p>光说不练假把式，我们实际测一下，就拿上面的图来做个测试吧。</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">const graph1 = new GraphG();</span><br><span class="line">graph1.addVertex(&quot;A&quot;);</span><br><span class="line">graph1.addVertex(&quot;B&quot;);</span><br><span class="line">graph1.addVertex(&quot;C&quot;);</span><br><span class="line">graph1.addVertex(&quot;D&quot;);</span><br><span class="line">graph1.addVertex(&quot;E&quot;);</span><br><span class="line">graph1.addVertex(&quot;F&quot;);</span><br><span class="line">graph1.linkVertex(&quot;A&quot;, &quot;B&quot;);</span><br><span class="line">graph1.linkVertex(&quot;C&quot;, &quot;B&quot;);</span><br><span class="line">graph1.linkVertex(&quot;D&quot;, &quot;B&quot;);</span><br><span class="line">graph1.linkVertex(&quot;C&quot;, &quot;D&quot;);</span><br><span class="line">graph1.linkVertex(&quot;D&quot;, &quot;E&quot;);</span><br><span class="line">graph1.linkVertex(&quot;E&quot;, &quot;F&quot;);</span><br><span class="line">graph1.linkVertex(&quot;A&quot;, &quot;F&quot;);</span><br><span class="line"></span><br><span class="line">const hamilton = new Hamilton(graph1);</span><br><span class="line">const result = hamilton.findHamiltonPath(); // [ &#x27;A&#x27;, &#x27;B&#x27;, &#x27;C&#x27;, &#x27;D&#x27;, &#x27;E&#x27;, &#x27;F&#x27;, &#x27;A&#x27;]</span><br></pre></td></tr></table></figure>

<p>通过测试验证代码是运行成功的。其实这个哈密尔顿回路是一个很经典的用到<code>递推</code>和<code>回溯</code>思想的案例，如果下一层不满足就往上回溯一层。直到递推到最底层。然后把最底层得到返回结果再一层一层地传递上去，最终会得到想要的结果。</p>

      
    </div>
    <div class="article-footer">
      <blockquote class="mt-2x">
  <ul class="post-copyright list-unstyled">
    
    <li class="post-copyright-link hidden-xs">
      <strong>本文链接：</strong>
      <a href="https://guoyayunhappy.gitee.io/didiblog/2024/03/03/find-hamilton-path/" title="Javascript实现寻找哈密尔顿回路" target="_blank" rel="external">https://guoyayunhappy.gitee.io/didiblog/2024/03/03/find-hamilton-path/</a>
    </li>
    
    <li class="post-copyright-license">
      <strong>版权声明： </strong> 本博客所有文章除特别声明外，均采用 <a href="http://creativecommons.org/licenses/by/4.0/deed.zh" target="_blank" rel="external">CC BY 4.0 CN协议</a> 许可协议。转载请注明出处！
    </li>
  </ul>
</blockquote>


<div class="panel panel-default panel-badger">
  <div class="panel-body">
    <figure class="media">
      <div class="media-left">
        <a href="https://gitee.com/GuoyayunHappy" target="_blank" class="img-burn thumb-sm visible-lg">
          <img src="/didiblog/images/avatar.jpg" class="img-rounded w-full" alt="">
        </a>
      </div>
      <div class="media-body">
        <h3 class="media-heading"><a href="https://gitee.com/GuoyayunHappy" target="_blank"><span class="text-dark">一枚@大帅锅</span><small class="ml-1x">CV工程师</small></a></h3>
        <div>个人简介。</div>
      </div>
    </figure>
  </div>
</div>


    </div>
  </article>
  
    
  <section id="comments">
  	
      <div id="vcomments"></div>
    
  </section>


  
</div>

  <nav class="bar bar-footer clearfix" data-stick-bottom>
  <div class="bar-inner">
  
  <ul class="pager pull-left">
    
    <li class="prev">
      <a href="/didiblog/2025/06/17/interview/" title="interview"><i class="icon icon-angle-left" aria-hidden="true"></i><span>&nbsp;&nbsp;上一篇</span></a>
    </li>
    
    
    <li class="next">
      <a href="/didiblog/2024/02/21/better-to-know-signature-and-certificate/" title="一文读懂加密，摘要，数字签名和证书"><span>下一篇&nbsp;&nbsp;</span><i class="icon icon-angle-right" aria-hidden="true"></i></a>
    </li>
    
    
  </ul>
  
  
  <!-- Button trigger modal -->
  <button type="button" class="btn btn-fancy btn-donate pop-onhover bg-gradient-warning" data-toggle="modal" data-target="#donateModal"><span>赏</span></button>
  <!-- <div class="wave-icon wave-icon-danger btn-donate" data-toggle="modal" data-target="#donateModal">
    <div class="wave-circle"><span class="icon"><i class="icon icon-bill"></i></span></div>
  </div> -->
  
  
  <div class="bar-right">
    
    <div class="share-component" data-sites="weibo,qq,wechat,facebook,twitter" data-mobile-sites="weibo,qq,qzone"></div>
    
  </div>
  </div>
</nav>
  
<!-- Modal -->
<div class="modal modal-center modal-small modal-xs-full fade" id="donateModal" tabindex="-1" role="dialog">
  <div class="modal-dialog" role="document">
    <div class="modal-content donate">
      <button type="button" class="close" data-dismiss="modal" aria-label="Close"><span aria-hidden="true">&times;</span></button>
      <div class="modal-body">
        <div class="donate-box">
          <div class="donate-head">
            <p>感谢您的支持，我会继续努力的!</p>
          </div>
          <div class="tab-content">
            <div role="tabpanel" class="tab-pane fade active in" id="alipay">
              <div class="donate-payimg">
                <img src="/didiblog/images/donate/alipayimg.png" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开支付宝扫一扫，即可进行扫码打赏哦</p>
            </div>
            <div role="tabpanel" class="tab-pane fade" id="wechatpay">
              <div class="donate-payimg">
                <img src="/didiblog/images/donate/wechatpayimg.png" alt="扫码支持" title="扫一扫" />
              </div>
              <p class="text-muted mv">扫码打赏，你说多少就多少</p>
              <p class="text-grey">打开微信扫一扫，即可进行扫码打赏哦</p>
            </div>
          </div>
          <div class="donate-footer">
            <ul class="nav nav-tabs nav-justified" role="tablist">
              <li role="presentation" class="active">
                <a href="#alipay" id="alipay-tab" role="tab" data-toggle="tab" aria-controls="alipay" aria-expanded="true"><i class="icon icon-alipay"></i> 支付宝</a>
              </li>
              <li role="presentation" class="">
                <a href="#wechatpay" role="tab" id="wechatpay-tab" data-toggle="tab" aria-controls="wechatpay" aria-expanded="false"><i class="icon icon-wepay"></i> 微信支付</a>
              </li>
            </ul>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>



</main>

  <footer class="footer" itemscope itemtype="http://schema.org/WPFooter">
	
	
    <ul class="social-links">
    	
        <li><a href="https://gitee.com/GuoyayunHappy" target="_blank" title="Github" data-toggle=tooltip data-placement=top><i class="icon icon-github"></i></a></li>
        
        <li><a href="/didiblog/atom.xml" target="_blank" title="Rss" data-toggle=tooltip data-placement=top><i class="icon icon-rss"></i></a></li>
        
    </ul>

    <div class="copyright">
    	
        <div class="publishby">
        	Theme by <a href="https://github.com/cofess" target="_blank"> cofess </a>base on <a href="https://github.com/cofess/hexo-theme-pure" target="_blank">pure</a>.
        </div>
    </div>
</footer>
  <script src="//cdn.jsdelivr.net/npm/jquery@1.12.4/dist/jquery.min.js"></script>
<script>
window.jQuery || document.write('<script src="js/jquery.min.js"><\/script>')
</script>

<script src="/didiblog/js/plugin.min.js"></script>


<script src="/didiblog/js/application.js"></script>


    <script>
(function (window) {
    var INSIGHT_CONFIG = {
        TRANSLATION: {
            POSTS: '文章',
            PAGES: '页面',
            CATEGORIES: '分类',
            TAGS: '标签',
            UNTITLED: '(未命名)',
        },
        ROOT_URL: '/didiblog/',
        CONTENT_URL: '/didiblog/content.json',
    };
    window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>

<script src="/didiblog/js/insight.js"></script>






   




   
    
  <script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/valine"></script>
  <script type="text/javascript">
  var GUEST = ['nick', 'mail', 'link'];
  var meta = 'nick,mail,link';
  meta = meta.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#vcomments',
    verify: false,
    notify: false,
    appId: '',
    appKey: '',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: meta,
    pageSize: '10' || 10,
    visitor: false
  });
  </script>

     







</body>
</html>